package com.hgx.algorithm.base.sort;

import com.hgx.algorithm.base.utils.ArraySortUtil;

/**
 * 堆排序
 * 时间复杂度O(N*logN)，额外空间复杂度O(1)
 * 如何找到当前的父节点和子节点
 * 1.父节点：(i -1)/2
 * 2.子节点：左 2*i+1  右 2*i+2
 * 堆结构非常重要
 * 1.堆结构的heapInsert与heapify
 * 2.堆结构的增大和减少
 * 3.如果只是建立堆的过程，时间复杂度为O(N)
 * 4.优先级队列结构，就是堆结构
 * 稳定性：不稳定
 */
public class HeapSort {

    public static void main(String[] args) {
        int[] arr = ArraySortUtil.generateRandomArray(30, 100);
        ArraySortUtil.print(arr);
        heapSort(arr);
        ArraySortUtil.print(arr);
    }

    /**
     * 堆排序实现
     *
     * @param arr 需要排序的数组
     */
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        //先调整成大根堆
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        //不断将最大的一个数弹出heapSize大小的堆外
        int heapSize = arr.length;
        ArraySortUtil.swap(arr, 0, --heapSize);
        while (heapSize > 0) {
            heapify(arr, 0, heapSize);
            ArraySortUtil.swap(arr, 0, --heapSize);
        }
    }

    /**
     * 建立大根堆
     *
     * @param arr   数组
     * @param index 坐标
     */
    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            ArraySortUtil.swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    /**
     * 当前位置的数减小时调整大根堆
     *
     * @param arr      数组
     * @param index    数减小的位置
     * @param heapSize 大根堆的大小
     */
    public static void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            //当最大的一个数不是自己时
            ArraySortUtil.swap(arr, largest, index);
            //位置来到交换的子节点
            index = largest;
            left = index * 2 + 1;
        }
    }
}
